#pragma once
#include<vector>
#include<time.h>
#include"stringObject.hpp"
namespace redisStruct
{
    struct SkiplistNode
    {
        int _key;
        stringObject* _val;
        std::vector<SkiplistNode*> _next;
        SkiplistNode(int level, int key , stringObject* val = nullptr) :_key(key), _val(val), _next(level, nullptr)
        {
            if (_val)
                _val->incrRefCount();
        };
        ~SkiplistNode()
        {
            if(_val)
            _val->decrRefCount();
        }
    };
    class Skiplist {

        typedef SkiplistNode Node;

    private:
        const int _maxLevel = 25;
        const double _p = 0.25;
        Node* _head = nullptr;
    public:
        Skiplist() {
            srand(time(0));
            _head = new Node(1, 0 , nullptr);
        }

        Node* search(int target) const  {

            Node* cur = _head;
            int level = _head->_next.size() - 1;
            while (level >= 0)
            {
                if (cur->_next[level] && cur->_next[level]->_key < target)
                    cur = cur->_next[level];
                else if (cur->_next[level] == nullptr || cur->_next[level]->_key > target)
                    level--;
                else
                    return cur->_next[level];
            }
            return nullptr;
        }

        void add(int num,stringObject* str) {
            std::vector<Node*> varry = findPre(num);
            int n = randomLevel();
            Node* newNode = new Node(n,num,str);
            if (n > _head->_next.size())
            {
                _head->_next.resize(n, nullptr);
                varry.resize(n, _head);
            }
            for (int i = 0; i < newNode->_next.size(); i++)
            {
                newNode->_next[i] = varry[i]->_next[i];
                varry[i]->_next[i] = newNode;
            }

        }

        bool erase(int num) {

            auto ret = findPre(num);
            if (ret[0]->_next[0] == nullptr || ret[0]->_next[0]->_key != num)
                return false;

            Node* pre = ret[0];
            Node* del = pre->_next[0];
            for (int i = 0; i < del->_next.size(); i++)
                ret[i]->_next[i] = del->_next[i];

            delete del;

            int level = _head->_next.size() - 1;
            while (level >= 0 && _head->_next[level] == nullptr)
            {
                level--;
            }
            _head->_next.resize(level + 1);
            return true;
        }

        

        int randomLevel() const 
        {
            int level = 1;
            while (rand() <= _p * RAND_MAX && level < _maxLevel)
            {
                level++;
            }
            return level;
        }

        std::vector<Node*> findPre(int val) const 
        {
            std::vector<Node*> varry(_head->_next.size(), _head);
            Node* cur = _head;
            int level = _head->_next.size() - 1;
            while (level >= 0)
            {
                if (cur->_next[level] && cur->_next[level]->_key < val)
                {
                    cur = cur->_next[level];
                }
                else if (cur->_next[level] == nullptr || cur->_next[level]->_key >= val)
                {
                    varry[level] = cur;
                    level--;
                }
            }
            return varry;
        }
        Node* begin() const
        {
            return _head;
        }
    };

}